package 图论.飞地的数量_1020;

import java.util.ArrayDeque;
import java.util.Deque;

/* 计算完全内陆的个数，可以用覆盖方法
   即先遍历四周如果有陆地那么就bfs，将与其相连的陆地都放入队列然后把陆地置为 海
   把个数重置
   最后遍历内陆，bfs将其个数计算出来
* */
public class Solution {
    static int ans = 0;
    static int[][] f = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
    public static void main(String[] args) {
        int[][] grid = {{0, 0, 0, 1, 1, 1, 0, 1, 0, 0}, {1, 1, 0, 0, 0, 1, 0, 1, 1, 1}, {0, 0, 0, 1, 1, 1, 0, 1, 0, 0}, {
                0, 1, 1, 0, 0, 0, 1, 0, 1, 0}, {0, 1, 1, 1, 1, 1, 0, 0, 1, 0}, {0, 0, 1, 0, 1, 1, 1, 1, 0, 1}, {
                0, 1, 1, 0, 0, 0, 1, 1, 1, 1}, {0, 0, 1, 0, 0, 1, 0, 1, 0, 1}, {1, 0, 1, 0, 1, 1, 0, 0, 0, 0}, {
                0, 0, 0, 0, 1, 1, 0, 0, 0, 1}};

        System.out.println(numEnclaves(grid));

    }
    static public int numEnclaves(int[][] grid) {
        // 把第一列置为海
        for (int i = 0; i < grid.length; i ++){
            if (grid[i][0] == 1){
                bfs(grid, i, 0);
            }
            // 把最后一列置为海
            if (grid[i][grid[0].length - 1] == 1){
                bfs(grid,i , grid[0].length - 1);
            }
        }
        // 把第1列置为海
        for (int j = 1; j < grid[0].length - 1; j ++){
            if (grid[0][j] == 1){
                bfs(grid, 0, j);
            }
            // 把最后一列置为海
            if (grid[grid.length - 1][j] == 1){
                bfs(grid, grid.length - 1, j);
            }
        }
        // 更新答案
        ans = 0;
        // 把范围里的计算答案并置为海
        for (int i = 1; i < grid.length - 1; i ++){
            for (int j = 1; j < grid[0].length - 1; j ++){
                if (grid[i][j] == 1) {
                    bfs(grid, i, j);
                }
            }
        }
        return ans;
    }

    static void bfs(int[][] grid, int x, int y){
        Deque<int[]> deque = new ArrayDeque<>();
        deque.offer(new int[]{x, y});
        ans ++;
        grid[x][y] = 0;
        while (!deque.isEmpty()){
            int[] t = deque.poll();
            for (int i = 0; i < 4; i ++){
                int dx = t[0] + f[i][0], dy = t[1] + f[i][1];
                if (dx < 0 || dy < 0 || dx >= grid.length || dy >= grid[0].length){
                    continue;
                }
                if (grid[dx][dy] == 1){
                    deque.offer(new int[]{dx, dy});
                    ans ++;
                    grid[dx][dy] = 0;
                }
            }
        }
    }

}
